/*
 * The utility function word_counter tokenizes an input string into words, then
 * prints the words that appeared in the input string and frequency of each
 * word's appearance in the input, sorted in the descending order of the
 * frequency.
 *
 * ---------- DESIGN CONSIDERATIONS --------------
 *
 * There are two fundamental tasks to be performed. First, parse the input
 * string for words and keep the count of frequency. Second, sort the
 * words in descending order of frequency and print. The code uses two
 * different data structure to perform these two tasks.
 * 
 * String comparison becomes expensive, in terms of time, to keep track
 * of how many times the word has appeared. Therefore, the utility function uses 
 * a hash table, which partly avoids comparing strings. Comparing strings
 * becomes inevitable if there is a hash key collision.
 * The algorithm also uses a linked list to scan words in a populated hash
 * table as scanning a sparsely populated hash table may cost lot of time.
 *
 * Once the input string is parsed for frequency, the data from a hash
 * table is converted in to a binary tree. This will help us optimize the
 * sorting of words based on frequency. Printing the result just boils down to
 * right to left tree traversal.
 *
 *
 * ---------- DESIGN CONSIDERATIONS --------------
 * 1. The input string to word_counter is NULL terminated.
 * 2. The thread safety is not required for this version.
 * 3. The code may not be reentrant-safe.
 * 4. Maintainer of the code understands the use case and the word_t buffer
 *    size can be changed by changing macro definition and recompiling the
 *    code.
 *
 */


#include "wordCounter.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>



/* 
 * make all pointers null
 */
void
init_hash_dictionary (hash_dictionary_t * dictionary)
{
  bzero (dictionary, sizeof (hash_dictionary_t));
}


/* 
 * Generates a hash key for the word based on sum of all the ASCII values
 * of the letters in the word. A special consideration is given to generate
 * different hash keys for words such as ABLE and BALE by adding first letter
 * to the hash key. This doesn't prevent hash key collision but avoid it to
 * some extent.
 */
int
get_hash_key (char *value)
{
  unsigned int key = 0;
  int i = 0;
  if (value == NULL || value[0] == '\0')
    return (-1);

  /*
   * Avoid generating same key for words such as ABLE and BALE
   */
  key = value[0];

  for (i = 0; (i < MAX_WORD_LEN) && (value[i] != '\0'); i++)
    {
      key = key + (unsigned int) value[i];
    }

  /* 
   * ASCII key for A is 65. For English word the key has to sum more
   * than 65
   */
  key = (key - 65) % _HASH_TABLE_LENGTH;
  return ((int) key);
}


/*
 * insert the word pointed to by value in the dictionary
 */


int
insert_in_hash_dictionary (hash_dictionary_t * dictionary, char *value)
{
  int hash_key = 0;
  word_t *word, *tword;


  if (!dictionary || !value)
    return (-1);
  if (value[0] == '\0')
    return (-2);

  /*
   * get hash key for the word
   */
  hash_key = get_hash_key (value);

  /* 
   * if there is is hash key collision then compare the word with
   * all the words in the collision chain for the hash key. If the
   * word already exists then increment the frequency counter.
   */
  if (dictionary->hash_table[hash_key] != NULL)
    {
      for (tword = dictionary->hash_table[hash_key];
	   tword != NULL;
	   tword = tword->hash_tree.hash_link.hash_collision_next)
	{
	  if ((!strncmp (value, tword->s_word, MAX_WORD_LEN))
	      && (tword->s_word[MAX_WORD_LEN] == value[MAX_WORD_LEN]))
	    {
	      tword->freq++;
	      return (0);
	    }
	}
    }
  word = malloc (sizeof (word_t));
  if (word == NULL)
    return (-3);
  strncpy (word->s_word, value, MAX_WORD_LEN);
  word->s_word[MAX_WORD_LEN] = '\0';
  word->freq = 1;

  /*
   * Add the word to hash table
   */
  word->hash_tree.hash_link.hash_collision_next =
    dictionary->hash_table[hash_key];
  dictionary->hash_table[hash_key] = word;

  /*
   * Add the word to linked list
   */
  word->hash_tree.hash_link.linked_list_next = dictionary->linked_list_head;
  dictionary->linked_list_head = word;
  return (0);
}

/* 
 * Builds a binary tree sorted on frequency (i.e word_t.freq).
 * On each word found in linked list, removes the word from
 * the linked list and inserts it into the binary tree
 */
word_t *
build_tree_from_dictionary (hash_dictionary_t * dictionary)
{
  word_t *temp_root = NULL;
  word_t *temp_node, *node;

  for (temp_node = dictionary->linked_list_head; temp_node != NULL;)
    {
      if (temp_root == NULL)
	{
	  temp_root = temp_node;
	  temp_node = temp_node->hash_tree.hash_link.linked_list_next;
	  temp_root->hash_tree.tree.left_node = NULL;
	  temp_root->hash_tree.tree.right_node = NULL;
	}
      else
	{
	  node = temp_node;
	  temp_node = temp_node->hash_tree.hash_link.linked_list_next;
	  /* 
	   * remove the node from linked list and add to the tree
	   */
	  node->hash_tree.tree.left_node = NULL;
	  node->hash_tree.tree.right_node = NULL;
	  insert_tree_node (temp_root, node);
	}
    }
  return (temp_root);
}

/*
 * A simple recursive routine to add a node to binary tree
 */

void
insert_tree_node (word_t * top, word_t * node)
{
  if (top == NULL || node == NULL)
    return;
  if (top->freq > node->freq)
    {
      if (top->hash_tree.tree.left_node == NULL)
	{
	  top->hash_tree.tree.left_node = node;
	  node->hash_tree.tree.right_node = NULL;
	  node->hash_tree.tree.left_node = NULL;
	  return;
	}
      else
	insert_tree_node (top->hash_tree.tree.left_node, node);
    }
  else
    {
      if (top->hash_tree.tree.right_node == NULL)
	{
	  top->hash_tree.tree.right_node = node;
	  node->hash_tree.tree.right_node = NULL;
	  node->hash_tree.tree.left_node = NULL;
	  return;
	}
      else
	insert_tree_node (top->hash_tree.tree.right_node, node);
    }
}


/*
 * Parses a tree and prints it to output file stream
 * Right. Center. Left.
 */
void
print_tree (word_t * tree_root, FILE * output)
{
  if (tree_root == NULL)
    return;
  print_tree (tree_root->hash_tree.tree.right_node, output);
  fprintf (output, "%s: %d\n", tree_root->s_word, tree_root->freq);
  print_tree (tree_root->hash_tree.tree.left_node, output);
  return;
}

/*
 * A place holder routine, which can be improved to add cleanup
 * tasks like deallocate space or make references null when not
 * in use.
 * Allows enhancing the routine in future.
 */
int
cleanup ()
{
  return (0);
}

int
count_words (char *input, FILE * output)
{
  char tvalue[1024];
  int n;
  hash_dictionary_t dictionary;
  word_t *tree_root;

  if ((input == NULL) || (output == NULL))
    {
      fprintf (stderr, "Invalid argument: Argument NULL");
      return (1);
    }

  init_hash_dictionary (&dictionary);

  while (sscanf (input, "%1023s%n", tvalue, &n) == 1)
    {
      if (n > MAX_WORD_LEN)
	{
	  fprintf (stderr,
		   "Current implementation supports word length of %d.\n",
		   MAX_WORD_LEN);
	  cleanup ();
	  return (1);
	}
      insert_in_hash_dictionary (&dictionary, tvalue);
      input += n;		/* advance the pointer by the number of characters read */
      if (*input == '\0')
	break;
      ++input;			/* skip the delimiter */
    }
  tree_root = build_tree_from_dictionary (&dictionary);
  print_tree (tree_root, output);
  return 0;
}



/* int
main ()
{
  char *str = "a a b b b c d e e e e e f f g g g g";
  return (count_words (str, stdout));
}*/
